#include <stdio.h>
#include "tree.h"

//递归中序遍历
void recursion_inorder_traverse(TreeNode *node) {
    if (node) {
        //遍历节点的左孩子
        if (node->left_child) {
            recursion_inorder_traverse(node->left_child);
        }
        //打印节点的数据
        display_tree_node(node);
        //遍历节点的右孩子
        if (node->right_child) {
            recursion_inorder_traverse(node->right_child);
        }
    }
}

int top = -1;

//获取栈顶元素
TreeNode *get_top(TreeNode **a) {
    if (top == -1) {
        return NULL;
    }
    return a[top];
}

//弹栈
void pop() {
    if (top > -1) {
        top--;
    }
}

//入栈
void push(TreeNode **a, TreeNode *node) {
    a[++top] = node;
}

void stack_traverse(TreeNode *node) {
    //先定义一个栈
    TreeNode *a[20];
    //把初始节点入栈
    push(a, node);
    TreeNode *temp;
    //执行遍历栈的操作
    while (top != -1) {
        while ((temp = get_top(a)) && temp) {
            push(a, temp->left_child);
        }
        pop();
        if (top != -1) {
            temp = get_top(a);
            pop();
            display_tree_node(temp);
            push(a, temp->right_child);
        }
    }
}

//中序遍历实现的另一种方法
void inorder_traverse_two(Tree tree) {
    TreeNode *a[20];//定义一个顺序栈
    TreeNode *p;//临时指针
    p = tree;
    //当p为NULL或者栈为空时，表明树遍历完成
    while (p || top != -1) {
        //如果p不为NULL，将其压栈并遍历其左子树
        if (p) {
            push(a, p);
            p = p->left_child;
        }
            //如果p==NULL，表明左子树遍历完成，需要遍历上一层结点的右子树
        else {
            p = get_top(a);
            pop();
            display_tree_node(p);
            p = p->right_child;
        }
    }
}


int main() {
    //创建一棵树
    Tree tree;
    create_tree(&tree);
    printf("The first data of the tree : %d \n", tree->data);
    display_tree_node(tree);
    printf("\n");
    printf("递归中序遍历\n");
    recursion_inorder_traverse(tree);
    printf("\n");
    printf("栈实现中序遍历\n");
    stack_traverse(tree);
    printf("\n");
    printf("栈实现中序遍历2\n");
    inorder_traverse_two(tree);

    return 0;
}
